/*
Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and set.

get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
set(key, value) - Set or insert the value if the key is not already present. When the cache reached its capacity, 
                  it should invalidate the least recently used item before inserting a new item.
*/

class LRUCache{
public:
    struct Entry{
        int key; 
        int value; 
        Entry(int k, int v) {key=k; value=v;} 
    };
    LRUCache(int capacity) {
        _nelems = 0; // zero elems
        _capacity = capacity;
    }
    int get(int key) {
        auto it = _CMap.find(key);
        if (it == _CMap.end()) return -1; // no elem
        Entry &e = *(it->second);
        // move the item to front of list
        _CList.splice(_CList.begin(), _CList, it->second);
        return e.value;
    }
    void set(int key, int value) {
        auto it = _CMap.find(key);
        if (it == _CMap.end()) {
            if (_nelems == _capacity) pop_lru();
            Entry e(key, value);
            _CList.push_front(e); // add to front of list
            _CMap[key] = _CList.begin();
            _nelems ++;
        } else {
            // move the item to front of list
            _CList.splice(_CList.begin(), _CList, it->second);
            Entry &e= *(_CList.begin());
            e.value = value; // set to new value
        }
    }
    void pop_lru() {
        // remove the last elem in the list
        Entry &e = _CList.back();
        _CMap.erase(e.key);
        _CList.pop_back();
        _nelems --;
    }
private:
    int _nelems;
    int _capacity;
    list<Entry> _CList;
    map<int, list<Entry>::iterator> _CMap;
};
